from operator import attrgetter

class ConverterException(Exception):
    pass

class Conversion(object):
    """Stores information about a Unit and a calculation how to get there."""
    def __init__(self, unit, calc):
        self._unit = unit
        self._calc = calc

    unit = property(attrgetter("_unit"))
    calculator = property(attrgetter("_calc"))

class ConversionChain(object):
    """A chain of conversions."""
    def __init__(self, head, tail = None):
        self._head = head
        self._tail = tail

    head = property(attrgetter("_head"))
    tail = property(attrgetter("_tail"))

    def has_converter(self, unit):
        """Tells if this chain contains a conversion to `unit`,
        instance of Unit."""
        return (self._head.unit == unit or
                (self._tail is not None and self._tail.has_converter(unit)))

    def convert(self, value):
        """Performs all the chained calculations in sequence with the given
        value as the starting point."""
        return self._head.calculator(
            self._tail.convert(value) if self._tail is not None else value)

    def __unicode__(self):
        return u"<ConversionChain %s %s %s>" % (
            self._head.unit.name,
            self._head.calculator,
            self._tail if self._tail is not None else "()")

def find_conversion_path(acc, goal):
    """Recursively try to find a conversion path starting with the
    ConversionChain instance acc to the Unit goal."""
    for edge in acc.head.unit.edges:
        if edge.unit == goal:
            return ConversionChain(edge, acc)
        elif not acc.has_converter(edge.unit):
            res = find_conversion_path(ConversionChain(edge, acc), goal)
            if res.head != edge:
                return res
    return acc

def identity(x):
    return x

# TODO: those exceptions aren't going to work
def find_converter(start, goal):
    if start is None:
        raise ConverterException("start was None")
    if goal is None:
        raise ConverterException("goal was None")
    startchain = ConversionChain(Conversion(start, identity))
    if (start == goal):
        return startchain
    solution = find_conversion_path(startchain, goal)
    return solution if startchain != solution else None

class ConverterFactory(object):
    def __init__(self, unitgraph, translations):
        self._unitgraph = unitgraph
        self._translations = translations

    def get_converter(self, fromid, toid):
        start = self._unitgraph.get(fromid, None)
        goal = self._unitgraph.get(toid, None)
        return find_converter(start, goal)

    def get_converter_localized(self, fromid, toid, locale):
        translation = self._translations.get(locale, None)
        if translation is None:
            raise ConverterLocaleException(
                "Unknown locale requested for converter: %s", locale)
        def gdicts(dicts, key, default):
            for dict in dicts:
                if dict.has_key(key):
                    return dict[key]
            return default
        dicts = (translation, self._unitgraph)
        start = gdicts(dicts, fromid, None)
        goal = gdicts(dicts, toid, None)
        return find_converter(start, goal)

    known_locales = property(lambda self: set(self._translations.keys()))
    unit_names = property(lambda self: set(self._unitgraph.keys()))

    def has_locale(self, locale):
        return self._translations.has_key(locale)

    def get_translated_unit_names(self, locale):
        translation = self._translations.get(locale, None)
        if translation is None:
            raise ConverterLocaleException("Unknown locale: %s", locale)
        return set(translation.keys())

